The Spanning Tree Protocol is a network protocol which is designed to maintain a loop-free topology in a bridged local area network. A family of spanning tree protocols is defined in IEEE 802.1D (802.1D-2004-IEEE Standard for Local and metropolitan area networks: Media Access Control (MAC) Bridges) and IEEE 802.1Q (802.1 Q-2011-IEEE Standard for Local and metropolitan area networks—Media Access Control (MAC) Bridges and Virtual Bridged Local Area Networks), the content of which is incorporated herein. These protocols are widely deployed in Ethernet networks.
The family of Spanning Tree Protocols includes the original Spanning Tree Protocol (STP), Rapid Spanning Tree Protocol (RSTP) and Multiple Spanning Tree Protocol (MSTP). RSTP is an extension of the original STP and provides significantly faster conversions after a change in the topology of a network. MSTP is a further extension to RSTP to allow it to construct different active topologies for different VLANs which can be useful for load balancing traffic. The configuration and operation of these protocols is defined by the IEEE standards mentioned above as a series of interconnected state machines. FIG. 1 shows FIG. 13-13 from IEEE 802.1Q-2011 (page 354). This figure shows the series of interconnected state machines used to operate the STP protocols.
The basic function of the Spanning Tree Protocol is to allow the bridges (sometimes referred to as switches) of a Bridged Local Area Network (referred to as a network herein) to collectively determine a spanning tree for controlling communication across the network. Such a spanning tree ensures that there are unique paths between all bridges on the network and avoids the formation of loops. Loops are particularly disadvantageous in such networks as frames can end up being endlessly switched around the network leading to saturation of the network capacity and potentially complete failure of the network. It is therefore extremely important that such loops are avoided.
The Spanning Tree Protocol is therefore used to establish a spanning tree based on the current layout and state of the elements of a network. However, the topology of a network can change. The removal of a bridge from a network or even one the disabling of port on a bridge, may result in the path between two elements on the network being removed. It would therefore be necessary for the spanning tree to be modified or recalculated to provide an alternative link path between each of the elements of the network to allow continued communication between them. This active responsiveness to changes in topology requires active monitoring and maintenance using the Spanning Tree Protocol.
As indicated above, the bridges collectively compute the spanning tree, with each bridge making its own calculations to determine which ports on that bridge are used for what purpose. Each bridge will therefore have to run the state machines shown in FIG. 1 in order to establish how it should manage its own ports. It will then communicate with other bridges in the network using special frames called Bridge Protocol Data Units (BPDUs) to exchange information about themselves and the network with other bridges in the network.
For example, the network initially needs to determine a root bridge which acts as the root of the spanning tree. Once the root bridge has been determined, each bridge then determines the least cost path to the root bridge, to establish which port is connected to the path that has the least cost to the root bridge. That port is then determined as the root port and communication with the root bridge will be made through that port.
For each Local Area Network (LAN) connected to ports on two or more bridges, it is necessary to determine a designated port for that LAN on a suitable bridge. Thus for a given LAN connected to two or more bridges, one of the ports on one of the bridges will be determined to be the designated port for that LAN and communication between that LAN and the root bridge will pass through the designated port. For each LAN, if the bridge with the port selected as the designated port for that LAN has any other ports to the same LAN, these ports are determined to be backup ports. Once the root ports, designated ports and backup ports have been determined, the remaining ports will normally be selected as alternate ports (although some versions of the standard allow different port roles to be defined). Ports with roles Alternate or Backup are blocked, meaning that frames are not switched through those ports.
The configuration of the spanning tree for a given network is defined in detail in the IEEE standards mentioned above.
From the above, it will be apparent that when a network is initially configured or when the topology has changed, a significant amount of calculation must be done to establish the correct states for the bridge and its ports. This is done by running the state machines shown in FIG. 1, as defined in the IEEE standard. As part of this, a considerable amount of information must be exchanged between the bridges so that each bridge can collect suitable information about which bridge is to be the root, the path cost to the root and so on. In order to establish the state of the bridges, the state machines in each bridge run until they reach a stable state. Once the state machines in all the bridges are stable, then it can be said that the network has reached steady state, at that moment in time.
However such a stable state may be disturbed by some event which requires the status of the spanning tree state machines to be reviewed, for example the reception of an external input such as a timer pop, a received packet, or a port going down. Such input events cause the state machines to run again until they reach a stable state. It will be appreciated that when one part of a network changes then this may trigger the state machines in one bridge to run and potentially determine a different set of conditions/states. This will be communicated using BPDU frames to advise the other bridges in the network of the change in its state. The reception of such frames by other bridges will cause them to run their own state machines until they again reach a stable state based on the newly received information. It will be appreciated that the changes may create a cascade of changes of state in other bridges as each of the bridges recalculate their own states and issue BPDU frames to other bridges which in turn cause them to calculate their own state and so on.
As will be apparent from the state machines shown in FIG. 1, when it is necessary to run the state machines there is a considerable processing load in order to complete the task. Some of the state machines have to be run for each port on the bridge, so where there are a large number of ports, this can be quite an onerous task for the processor carrying out the operation. It is therefore desirable to distribute the operation of the protocol across multiple components. This is desirable as it can be used to transfer some of the processing load from a central controller to other elements, for example, line cards within a bridge or processors in a multi-core CPU.
FIG. 2 shows schematically the layout for a bridge 1. The bridge includes a central controller card 2 and a plurality of line cards 3 (only three are shown in FIG. 2). Each of the line cards may include one or more separate ports 4. The state machines of the STP protocol can be allocated to different parts of the bridge, some to the central controller card 2 and some to the line cards 3 rather than all the state machines being run on the central controller 2. By offloading protocol operations to the line cards, the load on the central controller card 2 can be reduced such that at steady state, those components of the protocol operation allocated to the line cards perform all of the work with little or no load on the central controller card.
By distributing components of the protocol operation to line cards, delays in receiving, processing and sending bridging protocol data units (BPDUs) can be minimised. If all these frames had to be processed by a central controller card, there is a risk that a delay may be introduced in processing these frames and such delay could result in the creation of a switching loop within the network which, as indicated above, is potentially catastrophic to the operation of the network.
However, the spanning tree protocol specifies the internal operation of the protocol within each bridge in terms of multiple interconnected state machines. The operation of a given state machine may depend upon variables and states determined by one or more of the other state machines. Consequently the complex interconnectedness of these machines makes dividing them between distributed elements difficult. Simply allocating some of the state machines to the line cards whilst allocating some of the state machines to the central controller card will create logistical problems because a state machine running on a line card may require information from the operation of a state machine on the central controller and vice versa. All such splits result in excessive communication between the central controller and the line cards which detrimentally affects the operation of the overall system and may result in a delay in achieving a stable state. Furthermore, unless the interaction between the state machines is carefully controlled and synchronised, it may cause a switching loop to develop, with disastrous consequences for the network.
It is therefore an aim of the present invention to overcome or at least ameliorate some of the problems referred to above.